package sort

type ThreeWayQuickSort struct {
	BaseSort
}

func (self ThreeWayQuickSort) Sort() {
	self.sort(self.Array, 0, self.Len()-1)
}

//递归实现排序
func (self ThreeWayQuickSort) sort(array []int, left, right int) {
	// 递归结束条件
	if left >= right {
		return
	}

	//标定点所处的位置索引
	p := self.partition(array, left, right)
	self.sort(array, left, p-1)
	self.sort(array, p+1, right)

}

// 总体思路是将数组分为三个部分 大于标定数，等于标定数 和小于标定数三个部分，从数组两边开始遍历
func (self ThreeWayQuickSort) partition(array []int, left int, right int) int {
	var v = array[left]

	i := left + 1
	j := right

	for true {
		for i <= right && array[i] < v {
			i++
		}
		for j >= left+1 && array[j] > v {
			j--
		}
		if i > j {
			break
		}
		array[i], array[j] = array[j], array[i]

	}
	array[j], array[left] = array[left], array[j] //将标定点元素放到正确位置
	return j
}

func (self ThreeWayQuickSort) Name() string {
	return "三路快速排序"
}
